<!DOCTYPE group PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<group>

<p><b>VLFeat</b> includes a fast SVM solver, called 
<code>vl_svmpegasos</code>. The function implements the Pegasos SVM 
algorithm <a href="#ref1">[1]</a>, with a few adds such online 
Homogeneous kernel map expansion and SVM online statistics. </p> 

<!-- <p>Pegasos SVM <a href="#ref1">[1]</a> is implemented in <b>VLFeat</b> -->
<!--   by the function  <code>vl_svmpegasos</code>. Compared to the -->
<!--   original formulation, this implementation has some extras -->
<!--   features that allow memory efficiency and convergence analysis.</p> -->

<!-- <p>The use of online homogeneous kernel map<a href="#ref2">[2]</a> extensions reduces the  -->
<!--   memory usage up to the order of <i>n</i>, where <i>n</i> is the period of -->
<!--   the map. </p> -->

<!-- <p>In many  applications it is not clear which parameters and maps give -->
<!--   the best result, and one has to find the best setting via a series -->
<!--   of trials. <code>vl_svmpegasos</code> makes this process easier, -->
<!--   offering the possibility to check a set of statistics during the SVM -->
<!--   learning. </p> -->

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.pegasos">Pegasos SVM</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->



<p>A simple example on how to use <code>vl_svmpegasos</code> is presented below. Let's first build the training data  </p>
<precode type='matlab'>
% Set up training data
Np = 200 ;
Nn = 200 ;

Xp = diag([1 3])*randn(2, Np) ;
Xn = diag([1 3])*randn(2, Nn) ;
Xp(1,:) = Xp(1,:) + 2  ;
Xn(1,:) = Xn(1,:) - 2  ;

X = [Xp Xn] ;
y = [ones(1,Np) -ones(1,Nn)] ;
</precode>
<p>Plotting <i>X</i> and <i>y</i> we have </p>
<div class="figure">
 <img src="%pathto:root;demo/pegasos_training.jpg"/>
 <div class="caption">
  <span class="content">
   Training Data.
  </span>
 </div>
</div>

<p>Learning a linear classifier can be easily done with the following 2
lines of code:</p>

<precode type='matlab'>
dataset = vl_maketrainingset(X, int8(y)) ;
[w b info] = vl_svmpegasos(dataset, 0.01, ...
                           'MaxIterations',5000) ;
</precode>

<p>where we first create a struct containing the training data
using  <code>vl_maketraining data</code> and then we call the the SVM
solver. The output model <code>w</code> is plotted over the training
  data in the following figure. </p>

<div class="figure">
 <img src="%pathto:root;demo/pegasos_res.jpg"/>
 <div class="caption">
  <span class="content">
   Learned model.
  </span>
 </div>
</div>

<p> The output <code>b</code> is equal to <code>0</code> since the
  training data admits an SVM model passing from the origins. </p>

<p> The output <code>info</code> is a struct containing some
  statistic on the learned SVM: </p>


<precode type='matlab'>
info = 

           dimension: 2
          iterations: 5000
       maxIterations: 5000
             epsilon: -1
              lambda: 0.0100
      biasMultiplier: 0
    biasLearningRate: 1
     energyFrequency: 100
         elapsedTime: 0.0022
              energy: 0.1727
     regularizerTerm: 0.0168
             lossPos: 0.1003
             lossNeg: 0.0556
         hardLossPos: 0.1050
         hardLossNeg: 0.0750
</precode>

<p>It is also possible to  use under some
  assumptions<a href="#ref2">[2]</a> an homogeneous kernel map expanded online inside the
  solver. This can be done with the following command:  </p>

<precode type='matlab'>
dataset = vl_maketrainingset(X, int8(y).'homkermap',2,'KChi2') ;
</precode>

<p>The above code creates a training set without applying any
  homogeneous kernel map to the data. When the solver is called  it will expand each data point with a Chi Squared kernel
  of period 2.</p>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.pegasos.diagn">Real-time diagnostics</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p>VLFeat allows to get statistics during the training process. It is
  sufficient to pass a function handle to the solver. The function
  will be then called every <code>energyFrequency</code> time.</p>

<p>The following function simply plots the SVM energy values for all
  the past iterations: </p>

<precode type='matlab'>
function energy = diagnostics(svm,energy)
  figure(2) ; 
  energy = [energy svm.energy] ;
  plot(energy) ;
  drawnow ;
</precode>

<p>The energy value for the past iterations are kept in the
  row vector <code>energy</code>. The following code produces a plot of the energy value in real-time during the learning process. </p>

<precode type='matlab'>
energy = [] ;
dataset = vl_maketrainingset(X, int8(y)) ;
[w b info] = vl_svmpegasos(dataset, lambda, ...
                           'MaxIterations',5000,...
                           'DiagnosticFunction',@diagnostics,...
                           'DiagnosticCallRef',energy) ;

</precode>

<div class="figure">
 <img src="%pathto:root;demo/pegasos_energy.jpg"/>
 <div class="caption">
  <span class="content">
   SVM real-time energy values plot.
  </span>
 </div>
</div>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.dsift.references">References</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<ul>
  <li id="ref1">[1] Y. Singer and N. Srebro <em>Pegasos: Primal
  estimated sub-gradient solver for SVM</em> In Proc. ICML,
  2007.
</li>
<li id="ref2">[2] A. Vedaldi and A. Zisserman. <em>Efficient additive
    kernels via explicit feature maps</em>. In PAMI, 2011. 
</li>
</ul>

</group>
